package LeetCode._04动态规划_;

import java.util.Arrays;

public class _300_最长递增子序列 {
    /*
        dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
        1.明确base case dp(i) == 1
        2.明确状态:每一个dp[i]
        3.明确选择:每次在之前的子序列中进行循环遍历
        4.明确dp(i):dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
     */
    public int lengthOfLIS(int[] nums) {
        //dp(i):表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1); //每一个以自己结尾的子序列长度都为1
        //对于每一种状态的每一种选择
        for(int i=1;i<nums.length;++i){
            //每一种状态选择了之后的最大值
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    //只要可以形成一个最大的子序列，将dp[i]进行更新
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i=0;i<dp.length;++i){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
